# -*- coding:utf-8 -*-
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None
# class Solution:
#     # 返回 RandomListNode
#     def Clone(self, pHead):
#         # write code here
#         if not pHead:
#             return None
#         p = pHead
#         res_c = self.help_clone(p)
#         self.help_r(res_c)
#         res = self.help_splite(res_c)
#         return res
#
#
#     def help_splite(self, node):
#         pn = ph = node.next
#         node.next=ph.next
#         node = node.next
#         while node:
#             ph.next =node.next
#             ph = ph.next
#             node.next = ph.next
#             node = node.next
#         return pn
#
#     def help_clone(self, node):
#         if not node:
#             return None
#         n = node
#         while n:
#             t = RandomListNode(n.label)
#             t.next = n.next
#             n.next = t
#             n = t.next
#         return node
#
#     def help_r(self, node):
#         if not node:
#             return None
#         l = node
#         f = node.next
#         while f:
#             tmp = l.random
#             if tmp==None:
#                 f.random = None
#             else:
#                 f.random = tmp.next
#             f = f.next
#             l = l.next



class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        h = RandomListNode(0)
        l = pHead
        while l:
            new = RandomListNode(l.label)
            t = l.next
            new.next = l.next
            l.next = new
            l = t
        f1 = pHead
        f2 = pHead.next
        while f2:
            tmp = f1.random
            if tmp==None:
                f2.random = None
            else:
                f2.random = tmp.next
            f1 = f1.next
            f2 = f2.next
        p1 = p2 = pHead.next
        while p1.next:
            p1.next = p1.next.next
            p1 = p1.next
        h.next = p2
        return h.next


node1 = RandomListNode(1)
node2 = RandomListNode(3)
node3 = RandomListNode(5)
node1.next = node2
node2.next = node3
node1.random = node3

S = Solution()
clonedNode = S.Clone(node1)
print(clonedNode)
while clonedNode:
    print(clonedNode.label)
    clonedNode = clonedNode.next